#include <iostream>
#include <algorithm>
#include "TestSortHelper.h"
#include "SelectionSort.h"
#include "InsertSort.h"

using namespace std;

template <typename T>
void bubbleSort(T arrays[], int lenarray) {
	//优化版本1，记录在寻找最大值过程中是否有交换
	//若没有交换，则表明已经有序
	//对近乎有序的数据优化提升很快
	bool isswaped;
	do{
		isswaped = false;
		for (int j = 1;j < lenarray;j++) {
			if (arrays[j] < arrays[j - 1]) {
				swap(arrays[j], arrays[j - 1]);
				isswaped = true;
			}
		}
		lenarray--;
	} while (isswaped);

	//for ( int i = lenarray; i > 0; i-- ) {
	//	//for (int j = 0; j < i; j++) {
	//		//if (arrays[j] > arrays[i - 1]) {
	//			//swap(arrays[j], arrays[i - 1]);
	//		//}
	//	//}
	//	for (int j = 1;j < i;j++) {
	//		if (arrays[j] < arrays[j - 1]) {
	//			swap(arrays[j], arrays[j - 1]);
	//		}
	//	}
	//}
}

int main(){
	int n = 10000;
	cout << "Test for Random Array, size = " << n << ", randome range [0, " << n << "]" << endl;
	int *arr1 = TestSortHelper::generateRandomArray(n, 0, n);
	int *arr2 = TestSortHelper::copyIntArray(arr1, n);
	int *arr3 = TestSortHelper::copyIntArray(arr1, n);
	TestSortHelper::testSort("selection Sort", selectionSort, arr1, n);
	TestSortHelper::testSort("put Sort", insertSort, arr2, n);
	TestSortHelper::testSort("bubble Sort", bubbleSort, arr3, n);

	delete[] arr1;
	delete[] arr2;
	delete[] arr3;


	n = 10000;
	cout << "Test for Nearly Ordered Array, size = " << n << ", randome range [0, " << n << "]" << endl;
	arr1 = TestSortHelper::generateNearlyOrderedArray(n, 100);
	arr2 = TestSortHelper::copyIntArray(arr1, n);
	arr3 = TestSortHelper::copyIntArray(arr1, n);
	TestSortHelper::testSort("selection Sort", selectionSort, arr1, n);
	TestSortHelper::testSort("put Sort", insertSort, arr2, n);
	TestSortHelper::testSort("bubble Sort", bubbleSort, arr3, n);

	delete[] arr1;
	delete[] arr2;
	delete[] arr3;
}